A. Field of the Invention
The present invention relates to an IP (Internet Protocol) routing lookup scheme and system for multi-gigabit switching routers, especially to an IP routing lookup scheme and system which can guarantee 3 memory accesses in the worst case using a memory size less than 512 KB. Moreover, we can improve the performance of multi-gigabit switching routers greatly by pipeline skill in hardware.
B. Description of the Prior Art
The architecture of a multi-gigabit IP switching router is schematically shown in FIG. 1. It mainly includes a number of link interfaces 11, a CPU module 12, and a forwarding engine 13 interconnected with a switching fabric 14. The forwarding engine 13 employs a forwarding database which is a local version of the routing table downloaded from the CPU module 12 to make the routing decision. Although the routing updates may occur frequently, it is not necessary to download a new forwarding database for each routing update.
The CPU module 12 executes the routing protocols, such as RIP and OSPF, and needs a dynamic routing table for fast updates and fast generation of forwarding databases. For this reason, the forwarding database shall be optimized to furnish fast lookups.
The architecture of a forwarding engine 13 with superscalar scalar and pipeline design is shown in FIG. 2. An incoming IP packet will be buffered in the external data bus 21. The external data bus 21 is coupled to an internal data bus 22 for processing the incoming IP packet in the forwarding module 20. The forwarding module 20 includes a route lookup module 23, a header verification module 24, a header update module 26 and a MAC address substitution module 25. The route lookup module 23 reads the destination IP address of the incoming packet from the internal data bus 22. The IP header of the incoming packet is forwarded to the header verification module 24 and the header update module 26 to process at the same time. If the IP header of the incoming packet is not correct, the packet will be dropped. The lookup is then terminated. If the IP header is correct, the header verification module 24 will send a signal to the header update module 26 to update the decreased value of TTL and the recalculated checksum of the incoming IP packet via the external data bus 21. The route lookup module 23 will then provide the next hop (port number) for the incoming IP packet. The MAC address substitution module 25 then substitutes the source MAC address and the destination MAC address of the incoming IP packet by the MAC address of the output interface 11 and the immediate next hop (a router or the destination host) respectively. Then, the incoming IP packet can be forwarded into the output interface 11 via the external data bus 21.
According to the architecture as shown in FIG. 2, the bottleneck is in the route lookup module 23 because the header verification module 24, the header update module 26, and MAC address substitution module 25 all communicate with the route lookup module 23 to get the information for the forwarding next hop. The design of the rout lookup module 23 will significantly affect the packet forwarding rates and also the traffic on the networks.
Recent approaches on improving the packet forwarding rates shows that the IP lookup scheme is a tradeoff issue between memory size and access times. For instance, the most straightforward lookup scheme is to have a forwarding database containing every next hop for each 32-bit IP address. In this case, it requires only one memory access for IP address lookup. However, the Next Hop Array for an IP address of 32-bits directly spread for exact matching will need 4 GB (232=4 GB).
In another case, an indirect lookup approach is employed to reduce the size of forwarding database. As illustrated in FIG. 3, each IP address is partitioned into two parts: segment (16-bit) 31 and offset (16-bit) 34. The Segmentation Table (32-bit) 32 based on the segment 31 has the size of 64K for storing 65536 (216) entries. If the value of the entry of the Segmentation Table 32 is smaller than 256 (28), then it records the next hop of the routing. If the value of the entry of the Segmentation Table 32 is larger than 255, then it stores a pointer pointing to the associated Next Hop Array 33 (hereinafter referred to as NHA). Each NHA 33 has the size of 64K (216). Each entry in the NHA 33 is 8-bit for recording the next hop (port number) of the destination IP address. Thus, for a destination IP address a.b.x.y, the segment a.b can be an index for looking up the Segmentation Table 32 while the offset x.y an index for looking up the associated NHA, if necessary. In other words, for a segment a.b, if the length of the longest prefix for this segment is less than or equal to 16 (the segment length), then the corresponding next hop can be found in the Segmentation Table 32 without having to access the associated 64 KB NHA. On the other hand, if the length of the longest prefix is greater than 16, then a pointer in the Segmentation Table 32 can be found to point to an associated 64 KB NHA 33. According to this routing lookup mechanism, the maximum number of memory accesses for an IP address lookup is two with reduced memory size. Nevertheless, its memory requirement is still too big. In the worst case, it requires memory space of 4×64 KB+64K×64 KB for the segmentation table plus the NHA.
Some approach provides a software-based solution which can compress a table of 40,000 entries into 150–160 Kbytes. However, when this software is implemented in hardware, the memory accesses for a lookup is 2 in the best case and 9 in the worst case. Another approach provides a large size DRAM for fast routing lookup. The maximum number of memory accesses for a lookup can be reduced to 2 but with a forwarding table of 33 Mbytes. If an intermediate length table is added, the forwarding table can be reduced to 9 Mbytes, but the maximum number of memory accesses for a lookup will be increased to 3.
Another approach provides a lookup scheme based on the binary search mechanism. It requires a worst case time of log2(address bits) hash lookups. Thus, 5 hash lookups are needed for IPv4 and 7 for IPv6 (128-bit). This software based binary search work is further improved by employing the cache structure and using the multiway and multicolumn search. For a database of N prefixes with address length W, the native binary search scheme takes O(W*logN) searches. This improved schemes takes only O(W+logN) searches. However, these software-based binary search schemes are not easy to be implemented in hardware.